1. Field of the Invention
The present invention relates to the field of compression and decompression of data, in particular compression and decompression of digital image data.
2. Description of the Related Art
The benefits of compressing data are well-known. Compressing data in some instances saves storage space while in other instances it reduces data transmission time. Numerous techniques are known in the prior art for compressing and decompressing digital video data. For example, see U.S. Pat. No. 5,046,119 entitled "Method and Apparatus For Compressing and Decompressing Color Video Data With an Anti-Aliasing Mode", assigned to the assignee of the present invention. U.S. Pat. No. 5,046,119 describes a digital compression technique that is termed LOSSY. LOSSY data compression techniques concede a certain amount of lost accuracy of the image being represented in exchange for increased compression of the data. LOSSY compression techniques have proven to be effective when applied to graphical or video images and digitized audio data. Such LOSSY techniques operate on the premise that a certain amount of loss of accuracy is acceptable to efficiently represent an image or audio, i.e. analog, source in a digital format. Other LOSSY compression techniques for video image data are discussed by Nelson in "The Data Compression Book", M&T Books, a division of M&T Publishing, Inc., pp. 347-408, (1992).
Other known data compression techniques exactly replicate the original source data on decompression. Such data compression techniques are termed LOSSLESS. For example, see U.S. Pat. No. 4,558,302 entitled "High Speed Data Compression and Decompression Apparatus and Method". In a LOSSLESS data compression method, none of the data is lost during compression. LOSSLESS data compression techniques, are typically used for storing or transmitting textual data. Besides U.S. Pat. No. 4,558,302, known lossless compression techniques include, Huffman coding and various derivatives works on the well-known Lempel-Ziv compression algorithms.
LOSSLESS data compression techniques are generally regarded as unnecessary for video or audio data. Generally, this is due to the distribution of the data representing the video image or audio sound, and the time required for compressing/encoding the data into a compressed data stream.
LOSSLESS data compression for video image signals is desirable for implementations where the amount of data used to represent pixel shading values, is minimized. For example, with 8-bit color graphics, LOSSY compression may result in aliasing effects. Aliasing is the jagged or stair-step appearance of diagonal lines or circles in a video display. LOSSLESS data compression could be used to minimize such aliasing effects.
Thus, it is an object of the present invention to provide a LOSSLESS data compression/decompression technique for storing and retrieving digital image data.